﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0178_RightSideView : IAlgorithm
    {
        // 199. 二叉树的右视图

        // 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
        // [1,2,3,null,5,null,4] => [1,3,4]

        // 提示:
        //  二叉树的节点个数的范围是[0, 100]
        //  -100 <= Node.val <= 100 

        public void Test()
        {
            // 算法参数定义
            var root = new TreeNode(1, new TreeNode(2, null, new TreeNode(5)), new TreeNode(3, null, new TreeNode(4)));
            // 算法执行与打印
            var res = RightSideView(root);
            Console.Write(string.Join(' ', res));
        }

        // 算法
        public IList<int> RightSideView(TreeNode root)
        {
            var res = new List<int>();
            if (root == null) return res;
            var queue = new Queue<TreeNode>();
            queue.Enqueue(root);
            while (queue.Count > 0)
            {
                var curSize = queue.Count;
                for (int i = 0; i < curSize; i++)
                {
                    var tNode = queue.Dequeue();
                    if (i == 0)
                        res.Add(tNode.val);
                    if (tNode.right != null)
                        queue.Enqueue(tNode.right);
                    if (tNode.left != null)
                        queue.Enqueue(tNode.left);
                }
            }
            return res;
        }
    }
}
